package cn.zhxu.toys.concurrent;

/**
 * AbstractBloomFilter
 */
public abstract class AbstractBloomFilter implements BloomFilter {

	private Hasher hasher;
	private final long bitArrLength;		// 位数组的长度
	private final int hashFunCount;		// Hash 函数的个数
	
	public AbstractBloomFilter(int expectedInsertions, double fpp) {
		this(null, expectedInsertions, fpp);
	}
	
	public AbstractBloomFilter(Hasher hasher, int expectedInsertions, double fpp) {
		if (expectedInsertions < 1) {
			throw new IllegalArgumentException("expectedInsertions must greater than 0");
		}
		if (fpp <= 0 || fpp >= 1) {
			throw new IllegalArgumentException("fpp must greater than 0 and less than 1");
		}
		this.hasher = hasher;
		this.bitArrLength = optimalNumOfBits(expectedInsertions, fpp);
		this.hashFunCount = optimalNumOfHashFunctions(expectedInsertions, bitArrLength);
	}

	
	@Override
	public void put(String key, Object object) {
		long[] positions = new long[hashFunCount];
		for (int i = 0; i < hashFunCount; i ++) {
			long hash = hasher.hash(object, i);
			positions[i] = hash % bitArrLength;
		}
		updateBitArray(key, positions);
	}


	@Override
	public boolean mightContain(String key, Object object) {
		long[] positions = new long[hashFunCount];
		for (int i = 0; i < hashFunCount; i ++) {
			long hash = hasher.hash(object, i);
			positions[i] = hash % bitArrLength;
			
		}
		return checkBitArray(key, positions);
	}

	
	/**
	 * 更新位数组
	 * @param key 键
	 * @param positions 位置
	 */
	public abstract void updateBitArray(String key, long[] positions);
	
	/**
	 * 校验位数组
	 * @param key 键
	 * @param positions 位置
	 * @return true: 对应的位置是 1， false: 0
	 */
	public abstract boolean checkBitArray(String key, long[] positions);


	protected static long optimalNumOfBits(long n, double p) {
	    if (p == 0) {
	      p = Double.MIN_VALUE;
	    }
	    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
	}
	
	protected static int optimalNumOfHashFunctions(long n, long m) {
		// (m / n) * log(2), but avoid truncation due to division!
		return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
	}


	public Hasher getHasher() {
		return hasher;
	}

	public void setHasher(Hasher hasher) {
		this.hasher = hasher;
	}
	
}
